package com.lfg.leetcode.leetcode300;


import java.util.*;

public class No336palindromePairs {
    public static void main(String[] args) {
        List<List<Integer>> lists = palindromePairs(new String[]{"abcd", "dcba", "lls", "s", "sssll"});
        System.out.println(lists);
        lists = palindromePairs2(new String[]{"abcd", "dcba", "lls", "s", "sssll"});
        System.out.println(lists);
        lists = palindromePairs(new String[]{"bat", "tab", "cat"});
        System.out.println(lists);
        lists = palindromePairs2(new String[]{"bat", "tab", "cat"});
        System.out.println(lists);
        lists = palindromePairs(new String[]{"a", "ba", "ab", "b"});
        System.out.println(lists);
        lists = palindromePairs2(new String[]{"a", "ba", "ab", "b"});
        System.out.println(lists);

        List<List<Integer>> lists2 = palindromePairs(new String[]{"a", ""});
        System.out.println(lists2);
        lists2 = palindromePairs2(new String[]{"a", ""});
        System.out.println(lists2);
    }

    public static List<List<Integer>> palindromePairs(String[] words) {
        List<List<Integer>> ret = new ArrayList<>(words.length * words.length);
        Trie root = new Trie(' ');
        for (int index = 0; index < words.length; index++) {
            root.add(words[index], index);
        }
        for (int index = 0; index < words.length; index++) {
            root.search(words[index], index, ret);
        }
        return ret;
    }

    public static boolean palindrome(String str, int start, int end) {
        for (; start < end; start++, end--) {
            if (str.charAt(start) != str.charAt(end)) {
                return false;
            }
        }
        return true;
    }

    public static List<List<Integer>> palindromePairs2(String[] words) {
        Map<String, Integer> data = new HashMap<>(words.length);
        List<List<Integer>> ret = new ArrayList<>(words.length * words.length);
        for (int i = 0; i < words.length; i++) {
            data.put(words[i], i);
        }
        for (int index1 = 0; index1 < words.length; index1++) {
            String word = words[index1];
            int length = word.length();
            for (int i = 0; i <= length; i++) {
                if (i > 0 && palindrome(word, 0, i - 1)) {
                    String key = word.substring(i, length);
                    StringBuilder sb = new StringBuilder(key);
                    sb.reverse();
                    Integer index2 = data.get(sb.toString());
                    if (index2 != null && index2 != index1) {
                        ret.add(Arrays.asList(index2, index1));
                    }
                }
                if (palindrome(word, i, length - 1)) {
                    String key = word.substring(0, i);
                    StringBuilder sb = new StringBuilder(key);
                    sb.reverse();
                    Integer index2 = data.get(sb.toString());
                    if (index2 != null && index2 != index1) {
                        ret.add(Arrays.asList(index1, index2));
                    }
                }
            }
        }
        return ret;
    }

    public static class Trie {
        char c;
        Trie[] children = null;
        List<Integer> idx;
        Integer index = null;

        public Trie(char c) {
            idx = new ArrayList<>();
            this.c = c;
            children = new Trie[26];
        }

        public void add(String content, int i) {
            Trie root = this;
            int length = content.length();
            for (int index = length - 1; index >= 0; index--) {
                char c = content.charAt(index);
                int idx = c - 'a';
                if (root.children[idx] == null) {
                    root.children[idx] = new Trie(c);
                }
                if (palindrome(content, 0, index)) {
                    root.idx.add(i);
                }
                root = root.children[idx];
            }
            root.idx.add(i);
            root.index = i;
        }

        public void search(String content, int i, List<List<Integer>> ret) {
            Trie root = this;
            int length = content.length();
            for (int index = 0; index < length; index++) {
                if (root.index != null && palindrome(content, index, length - 1) && root.index != i) {
                    ret.add(Arrays.asList(i, root.index));
                }
                char c = content.charAt(index);
                root = root.children[c - 'a'];
                if (root == null) {
                    return;
                }
            }

            for (int num : root.idx) {
                if (num != i) {
                    ret.add(Arrays.asList(i, num));
                }
            }
        }
    }

}



